package 剑指offer;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:53:47 
* @Description：
* 
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字

数据范围：

	对于%50的数据,size<=10^4

	对于%75的数据,size<=10^5

	对于%100的数据,size<=2*10^5

示例1
输入
复制
1,2,3,4,5,6,7,0
输出
复制
7
*/
public class A35数组中的逆序对 {
	
	/*
	 * 实际上是一个分治问题，不断将数组一分为二，直到数组中只有两个元素
	 * ，统计逆序对个数，分别排序后进行合并
	 * ，merge的时候计算合并的两个数组间的逆序对个数。
	 * 类似归并排序的过程。
	 */

	
	private static int count;
	
	private  static void MergeSort(int [] arr,int start,int end) {
		if (start>=end) {
			return;
		}
		int mid=(start+end)>>1;
		MergeSort(arr, start, mid);
		MergeSort(arr, mid+1, end);
		Merge(arr, start, mid, end);
	}
	
	
	private static void Merge(int [] arr,int start,int mid,int end) {
		//临时数组用来存储
		int [] temp=new int[end-start+1];
		int k=0,i=start,j=mid+1;
		while(i<=mid&&j<=end) {
			//如果前面的元素小于后面的就不能构成逆序对
			if (arr[i]<=arr[j]) {
				temp[k++]=arr[i++];
			}else {
				//如果前面的元素大于后面的，那么在前面的元素之后的元素都可以和后面的元素构造逆序对
				temp[k++]=arr[j++];
				count=(count+(mid-i+1))%1000000007;
			}
		}
		
		while(i<=mid) {
			temp[k++]=arr[i++];
		}
		while(j<=end) {
			temp[k++]=arr[j++];
		}
		for(int m=0;m<k;m++) {
			arr[start+m]=temp[m];
		}
	}
	
public static  int InversePairs(int [] array) {
	MergeSort(array, 0, array.length-1);
	return count;
    }

public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	String s = scanner.nextLine();
	String[] ss = s.split(" ");
	int [] arr=new int [ss.length];
	for (int i = 0; i < arr.length; i++) {
		arr[i]=Integer.parseInt(ss[i]);
	}
	int pairs = InversePairs(arr);
	System.out.println(pairs);
}

/*
 * 1 2 3 4 5 6 7 0
7

 */

}
